// https://www.luogu.com.cn/problem/B3637
#include <bits/stdc++.h>
using namespace std;
int a[1000000];
int g[1000000];
// ：g[i]表示长度为i的所有上升子序列的结尾元素的最小值

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  g[0] = -1;
  int len = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] > g[len]) {
      len++;
      g[len] = a[i];

    } else {
      int k = lower_bound(g, g + len + 1, a[i]) - g;
      // lower_bound查找第一个大于等于a[i]的元素位置
      // 如果使用upper_bound（查找第一个大于a[i]的元素位置），会导致无法处理相等元素的情况，可能无法得到正确的最长上升子序列长度

      g[k] = a[i];
    }
  }

  /*   for (int i = 1; i <= len; i++) {
      cout << g[i] << endl;
    } */
  cout << len;

  return 0;
}
